package com.hy.study.huffmancode;


import java.io.*;
import java.util.*;
import java.lang.Comparable;

public class HuffmanCode {
    private final static String srcFile = "/Users/huyong/Downloads/world.sql";
    private final static String descFile = "/Users/huyong/Downloads/desc.zip";
    private final static String dsFile = "/Users/huyong/Downloads/world2.sql";
    private static StringBuffer buffer = new StringBuffer();
    //用于方法huffman 编码表
    private static Map<Byte, String> huffmanCodes = new HashMap<>();

    public static void main(String[] args) {
        zipFile(srcFile, descFile);
        System.out.println("～压缩文件成功");
        unZipFile(descFile, dsFile);
    }


    public static void main1(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentByte = content.getBytes();
        byte[] bytes = huffmanZip(contentByte);
        System.out.println(Arrays.toString(bytes));
        byte[] decode = decode(huffmanCodes, bytes);
        System.out.println(Arrays.toString(decode));
        System.out.println("还原后的字符串:" + new String(decode));


    }


    private static void unZipFile(String zipFile, String dsFile) {
        InputStream is = null;
        ObjectInputStream ois = null;
        OutputStream os = null;
        try {
            is = new FileInputStream(zipFile);
            ois = new ObjectInputStream(is);
            //读取byte数组  huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码标
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            byte[] decode = decode(huffmanCodes, huffmanBytes);
            os = new FileOutputStream(dsFile);
            os.write(decode);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            if (os != null) {
                try {
                    is.close();
                    is = null;
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    }

    /**
     * 压缩一个文件的方法
     *
     * @param srcFile 希望压缩的文件
     * @param desFile 压缩之后的目录
     */
    public static void zipFile(String srcFile, String desFile) {
        OutputStream os = null;
        InputStream is = null;
        ObjectOutputStream oos = null;
        try {
            os = new FileOutputStream(desFile);
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的数组
            byte[] b = new byte[is.available()];
            is.read(b);
            //直接得到处理之后的压缩字节码
            byte[] bytes = huffmanZip(b);
            //这里以对象流的方式写入赫夫曼编码，是为了以后我们恢复源文件时使用
            oos = new ObjectOutputStream(os);
            oos.writeObject(bytes);//写入压缩之后的文件
            oos.writeObject(huffmanCodes);//写入huffman 编码

        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            if (is != null) {
                try {
                    is.close();
                    is = null;
                } catch (Exception ise) {
                    System.out.println(ise.getMessage());

                }
            }
            if (os != null) {
                try {
                    os.close();
                    os = null;
                } catch (Exception ose) {
                    System.out.println(ose.getMessage());

                }
            }
            if (oos != null) {
                try {
                    oos.close();
                    oos = null;
                } catch (Exception ooe) {
                    System.out.println(ooe.getMessage());

                }
            }


        }

    }


    /**
     * 编写一个方法，完成对压缩数据的解码
     *
     * @param huffmanCode 赫夫曼编码标map
     * @param huffmanByte 赫夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCode, byte[] huffmanByte) {
        //1.先得到huffmanBytes 对应的二进制的字符串
        StringBuffer buffer = new StringBuffer();
        //2.将byte 数组转换成二进制字符串
        for (int i = 0; i < huffmanByte.length; i++) {
            boolean flag = (i == huffmanByte.length - 1);
            buffer.append(byteToBitString(!flag, huffmanByte[i]));
        }
        System.out.println(buffer.toString());
        //把字符串按照指定的赫夫曼编码进行解码
        HashMap<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCode.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        System.out.println(map);
        //创建集合存放byte
        ArrayList<Byte> bytes = new ArrayList<>();
        for (int i = 0; i < buffer.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //取出一个1或者0
                String key = buffer.substring(i, i + count);
                b = map.get(key);
                if (b == null) {//没有匹配到
                    count++;
                } else {
                    //找了
                    flag = false;
                }

            }
            bytes.add(b);
            i += count;//i 直接到下一个字符位置开始
        }
        //将list 中数组转换成byte[] 数组
        byte b[] = new byte[bytes.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = bytes.get(i);
        }
        return b;
    }

    /**
     * 将一个byte 转换成一个二进制字符串
     *
     * @param b    传入的byte值
     * @param flag 标识是否需要补高位,true 需要补高位 false 不需要补高位
     * @return 是该b 对应的二进制的额字符串，(是按照补码返回)
     */

    private static String byteToBitString(boolean flag, byte b) {
        //使用遍历 保存b
        int temp = b;//将b 转换成int
        //这里返回的是temp二进制的补码
        //如果是整数 需要补高位
        //如果是负数 需要截取低8位
        if (flag) {
            temp |= 256;//按位与 //256  -->1 0000 0000
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);//只要 最后8位 int 总共32位 返回补码，需要将补码转换成 源码

        } else {
            return str;
        }


    }


    /**
     * 将huffman 压缩提取成一个方法
     * 编码的时候按照补码来编码的
     *
     * @param bytes 原始的字节数组
     * @return 是经过huffman 编码处理后的字节数组(压缩后的数组)
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        Node hufufmanTree = createHufufmanTree(nodes);
        Map<Byte, String> huffmanCode = getCodes(hufufmanTree);
        byte[] zip = zip(bytes, huffmanCode);
        return zip;

    }

    private static Node createHufufmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //新创建的节点的值为空 权值为左右子节点的权重只和
            Node parentNode = new Node(leftNode.getWight() + rightNode.getWight());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);
            //将处理之后的节点删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将新的二叉树加入到二叉树重
            nodes.add(parentNode);
        }
        //nodes 最后的节点就是haffman 的跟节点
        return nodes.get(0);
    }

    private static List<Node> getNodes(byte[] contentByte) {
        ArrayList<Node> nodes = new ArrayList<>();
        //统计每个字符出现的次数
        Map<Byte, Integer> counts = new HashMap<>();

        for (byte b : contentByte) {
            Integer count = counts.get(b);
            if (count == null) {
                count = 1;
            } else {
                count++;
            }
            counts.put(b, count);
        }

        for (Byte b : counts.keySet()) {
            Integer count = counts.get(b);
            nodes.add(new Node(b, count));
        }
        return nodes;
    }

    private static void perOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("huffman is empty ");
        }
    }

    /**
     * 为了调用方便 重载方法
     */
    private static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //处理root 的左子树
        getCodes(root.getLeft(), "0", buffer);
        //处理右子树
        getCodes(root.getRight(), "1", buffer);
        return huffmanCodes;
    }

    /**
     * Map中存放huffman编码表 将传入的node 节点的叶子节点 的编码得到并放入到haffcode 集合中
     *
     * @param node   传入的节点
     * @param code   路径 : 左子节点 0,右子节点 1
     * @param buffer 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuffer buffer) {
        StringBuffer stringBuffer = new StringBuffer(buffer);
        //将code 加入
        stringBuffer.append(code);
        if (node != null) {
            //判断当前node 是叶子节点还是非叶子节点
            if (node.getData() == null) {
                //不是叶子节点   递归处理
                //向左
                getCodes(node.getLeft(), "0", stringBuffer);
                //向右
                getCodes(node.getRight(), "1", stringBuffer);
            } else {
                //是叶子节点 表示找到了某个叶子节点的最后
                huffmanCodes.put(node.getData(), stringBuffer.toString());
            }
        }
    }

    /**
     * 将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
     *
     * @param bytes       bytes 这时原始的字符串对应的byte[]
     * @param buffmancode huffmanCodes 生成的赫夫曼编码map
     * @return 最后爱生成字符串对应的byte 数组 8位一组 对应一个byte
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> buffmancode) {
        StringBuffer buffer = new StringBuffer();
        for (byte b : bytes) {
            buffer.append(huffmanCodes.get(b));
        }
        System.out.println(buffer.toString());
        //将上述二进制转换成byte[] 数组
        int len;
        if (buffer.length() % 8 == 0) {
            len = buffer.length() / 8;
        } else {
            len = buffer.length() / 8 + 1;
        }
        //上述代码一句话搞定
        // int len=(buffer.length()+7)/8;
        //创建存储压缩之后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;
        //因为是每8位对应一个byte 所以步长+8
        for (int i = 0; i < buffer.length(); i += 8) {
            String strByte;
            if (i + 8 > buffer.length()) {
                //最后一次不够8位
                strByte = buffer.substring(i);
            } else {
                strByte = buffer.substring(i, i + 8);
            }
            //将strByte 转换成char
            huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodeBytes;
    }

}

class Node implements Comparable<Node> {
    Byte data;//存放数据本身比如'a'=>97
    Integer wight;//权值，百事字符出现的次数
    Node left;
    Node right;

    public Node(Byte data, Integer wight) {
        this.data = data;
        this.wight = wight;
    }

    public Node(Integer wight) {
        this.wight = wight;
    }

    public Byte getData() {
        return data;
    }

    public void setData(Byte data) {
        this.data = data;
    }

    public Integer getWight() {
        return wight;
    }

    public void setWight(Integer wight) {
        this.wight = wight;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.wight - o.wight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", wight=" + wight +
                '}';
    }

    public void preOrder() {
        System.out.println(this);
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
            this.getRight().preOrder();
        }
    }
}
